package com.leetcode.二维数组查找;

/**
 * <p>
 * 二维数组查找问题：https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?tpId=13&tqId=11154&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
 * </p>
 *
 * @author: Sunny
 * @date: 2021/3/9
 * @version: v1.0.0
 */
public class Main {

    /**
     * 二维数组：
     * n2
     * 1 2 8 9
     * 2 4 9 10
     * 4 7 10 13
     * 6 8 11 15
     * n1
     */
    public static void main(String[] args) {
        int target = 7;
        int[][] array = {{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}};
        System.out.println(find(target, array));
    }

    /**
     * 二分查找：时间复杂度：O(N)
     * <p>
     * 利用二维数组由上到下，由左到右递增的规律，
     * 那么选取右上角或者左下角的元素a[row][col]与target进行比较，
     * 当target小于元素a[row][col]时，那么target必定在元素a所在行的左边,即col--；
     * 当target大于元素a[row][col]时，那么target必定在元素a所在列的下边,即row++；
     * <p>
     * 若二维数组有n行n列(注:n行n列中，对角线上的元素有√2*n个)，则需要查找√2*n次，故时间复杂度为O(n)
     *
     * @param target
     * @param array
     * @return
     */
    public static boolean find(int target, int[][] array) {
        int row = 0;
        int col = array[0].length - 1;
        while (row <= array.length - 1 && col >= 0) {
            if (target == array[row][col])
                return true;
            else if (target > array[row][col])
                row++;
            else
                col--;
        }
        return false;
    }

    /**
     * 时间复杂度：O(N^2)
     * @param target
     * @param array
     * @return
     */
//    public static boolean find(int target, int[][] array) {
//        // 将二维数组转换成集合
//        List<Integer> list = new ArrayList<>();
//        for (int i = 0; i < array.length; i++) {
//            for (int j = 0; j < array.length; j++) {
//                list.add(array[i][j]);
//            }
//        }
//        return list.contains(target);
//    }

}
